BZOJ4589 Hard Nim < FWT >

Problem

Hard Nim


Description

在玩石子游戏,他们有 堆石子,规则如下:

  1. 两个人轮流拿石子, 先拿。
  2. 每次只能从一堆中取若干个,可将一堆全取走,但不可不取,拿到最后1颗石子的人获胜。

不同的初始局面,决定了最终的获胜者,有些局面下先拿的 会赢,其余的局面 会负。
很好奇,如果这 堆石子满足每堆石子的初始数量是不超过 的质数,而且他们都会按照最优策略玩游戏,那么 能获胜的局面有多少种。
由于答案可能很大,你只需要给出答案对 取模的值。

Input

输入文件包含多组数据,以EOF为结尾。
对于每组数据,输入一行两个正整数

Output

对于每组数据,输出一行一个整数表示答案。

Sample Input

1
2
3 7
4 13

Sample Output

1
2
6
120

HINT

每组数据有 ,
不超过 组数据。

Source

Topcoder SRM 518 Div1 Hard Nim By Tangjz

标签:FWT

Solution

裸题。
由基础博弈可知, 游戏先手必胜的充要条件是所有石子堆个数异或和为 。于是答案为

预处理不超过 的质数,设有 个。设 为一个数组,其中 ,则 均为 。用 ,可知 。同理 。这样做 次即可得到 。最终答案为
注意到从 推到 是异或卷积的形式,于是可以用 优化,总复杂度

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define MAX_N 65536
#define P 1000000007
#define inv2 500000004
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
x = 0; int c = getchar(), f = 1;
for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, l, cnt, pri[MAX_N+5];
lnt a[MAX_N+5]; bool NotPri[MAX_N+5];
void init() {
NotPri[0] = NotPri[1] = true;
for (int i = 2; i <= MAX_N; i++) {
if (!NotPri[i]) pri[++cnt] = i;
for (int j = 1; j <= cnt; j++) {
if (i*pri[j] > MAX_N) break;
NotPri[i*pri[j]] = true;
if (i%pri[j] == 0) break;
}
}
}
lnt pow(lnt x) {
lnt ret = 1;
for (int k = n; k; k >>= 1, x = x*x%P)
if (k&1) ret = ret*x%P;
return ret;
}
void FWT(lnt *arr, int l) {
for (int d = 1; d < l; d <<= 1)
for (int i = 0; i < l; i += (d<<1))
for (int j = i; j < i+d; j++) {
lnt x = arr[j], y = arr[j+d];
arr[j] = (x+y)%P, arr[j+d] = (x-y+P)%P;
}
}
void UFWT(lnt *arr, int l) {
for (int d = l>>1; d; d >>= 1)
for (int i = 0; i < l; i += (d<<1))
for (int j = i; j < i+d; j++) {
lnt x = arr[j], y = arr[j+d];
arr[j] = (x+y)%P*inv2%P;
arr[j+d] = (x-y+P)%P*inv2%P;
}
}
int main() {
init();
while (~scanf("%d%d", &n, &m)) {
memset(a, 0, sizeof a); for (l = 1; l <= m; l <<= 1) ;
for (int i = 1; i <= cnt && pri[i] <= m; i++) a[pri[i]] = 1;
FWT(a, l); for (int i = 0; i < l; i++) a[i] = pow(a[i]);
UFWT(a, l); printf("%lld\n", a[0]);
}
return 0;
}
------------- Thanks For Reading -------------
0%